Understand how standard algorithms (bubble sort, merge sort, linear…

The idea

Four standard algorithms must be understood. Bubble sort repeatedly compares adjacent items in a list and swaps them when they are in the wrong order, so large values move to the end on each pass; passes repeat until a complete pass makes no swaps. Merge sort splits a list into single-item sublists, then repeatedly merges pairs of sorted sublists in order until one sorted list remains. Linear search checks each item from the start of a list in turn until the target is found or the list ends, so it works on unsorted data. Binary search requires a sorted list: it examines the middle item, then discards the half that cannot contain the target and repeats on the remaining half until the target is found or the search space is empty.

What earns the marks

• Bubble sort compares adjacent pairs and swaps them when out of order, repeating passes until a pass produces no swaps.
• Merge sort divides the list into single items, then merges sorted sublists pairwise in order until a single sorted list remains.
• Linear search examines items one at a time from the start until the target is found or the list is exhausted, and does not require sorted data.
• Binary search requires a sorted list, tests the middle item, then discards the half that cannot contain the target and repeats on the remaining half.
• Efficiency comparison: binary search is generally faster than linear search on large sorted lists, while linear search is the only option for unsorted data.
• Correct application: for a given list and target, state the items examined in order and the final result for each algorithm.

Common mistakes and how to put them right

• Using binary search on an unsorted list.

  Put it right: Binary search depends on sorted order, so the list must be sorted first or linear search used instead.

• Stopping bubble sort after one pass.

  Put it right: Passes continue until a complete pass makes no swaps, because one pass may not fully sort the list.

• Merging sublists in merge sort without comparing their items.

  Put it right: Merging must place items in order, comparing the front items of the sublists at each step.

• Skipping items in a linear search.

  Put it right: Linear search checks each item in turn from the start until the target is found or the list ends.

Exam tips

• For a given list, write out the state of the list after each pass or merge so the examiner can follow your working.
• State clearly whether a list must be sorted before an algorithm can be used, and name the algorithm that works on unsorted data.
• When comparing search algorithms, refer to the number of items examined rather than vague claims about speed.